수학, 분할 정복
위 문제를 풀기 위해서는 우선 피보나치의 항등식 중 하나인 도가뉴 항등식을 알아야한다.
도가뉴 항등식은 아래와 같이 정의된다.
이를 활용해 구하는 피보나치 수
에 대해 아래와 같이 2가지의 경우의 수로 나누어 값을 구할 수 있다.위 방법을 이용하면 피보나치 수를 구하는 연산을
의 속도로 구할 수 있다.도가뉴 항등식의 증명은 아래 사이트를 참고하길 바란다.
https://compy07.github.io/Blog/posts/algorithms/math/docagnes_identity/#22-수학적-귀납법을-이용한-증명
이제 피보나치 수를 구할 수 있으니,
까지의 피보나치 수의 제곱의 합을 구하는 방법을 설명하겠다.이번 문제에서는
로 정의했고, 피보나치에 대한 점화식과 이번 풀이에서 활용할 공식의 변형은 순서대로 아래와 같다.2번째 공식을 이용해
값을 구할 수 있다.우리가 구하는 값은
로 표현할 수 있다.그리고
를 위의 수식으로 바꾸고, 식은 전개하면 아래와 같다.고로, 겹치는 중간 값을 지워 보면
이 된다.여기서
이기 때문에, 최종적으로는
이다.이제 위 두가지 공식을 이용할 수 있다. 도가뉴 항등식을 이용해서 피보나치 수를 구하고, 제곱값의 합 공식을 이용해서 정답을 출력한다.